#include <iostream>
#include <vector>

using namespace std;

class Solution {
private:
    vector<string> ans;
    void dfs(string& str, int index, int score, int& max_score) {
        if (index == str.size()) {
            if (score == 0) {
                ans.push_back(str);
            }
            return;
        }
        if (score < max_score) {
            str[index] = '(';
            dfs(str, index + 1, score + 1, max_score);
        }
        if (score > 0) {
            str[index] = ')';
            dfs(str, index + 1, score - 1, max_score);
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        string str(2 * n, ' ');
        dfs(str, 0, 0, n);
        return ans;
    }
};